<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>环形链表</title>
  </head>
  <body>
    <div class="translate">
      是否拥有环：
      <br />
      可以考虑追击问题，当fast指针追击slow指针时，如果存在相遇则存在环
      <br />
      哈希表法，如果存在环，则必然存在重复的节点，因此可以采用哈希表存储节点，如果存在重复节点则存在环
    </div>
    <div id="container"></div>

    <script type="module">
      // import linkedList from './linkedList.js'

      class node {
        constructor(ele) {
          this.ele = ele // 内容
          this.next = null // 指针
        }
      }

      class linkedList {
        constructor() {
          this.head = new node('head') // 头节点
        }

        find(item) {
          let currentNode = this.head // head对象
          while (currentNode.ele !== item) {
            if (currentNode.next === null) {
              return null // 如果找不到节点，返回 null
            }
            currentNode = currentNode.next // 指针指向下一个节点
          }
          return currentNode
        }

        insert(newEle, item) {
          let newNode = new node(newEle)

          let currentNode = this.find(item)
          if (currentNode === null) {
            return
          }

          newNode.next = currentNode.next
          currentNode.next = newNode

          // 如果插入的节点指向头节点，形成环
          if (this.find(newEle)) {
            let targetNode = this.find(newEle)

            if (targetNode) {
              newNode.next = targetNode
            }
          }
        }

        remove(item) {
          let currentNode = this.head

          // 有下一个元素，不能是item元素本身
          while (currentNode.next !== null && currentNode.next.ele !== item) {
            currentNode = currentNode.next
          }
          if (currentNode.next !== null) {
            currentNode.next = currentNode.next.next
          }
        }

        update(item, newItem) {
          let currentNode = this.find(item)
          if (currentNode === null) {
            return
          }
          currentNode.ele = newItem
        }
      }

      const container = document.querySelector('#container')
      let head = new linkedList()
      head.insert('a', 'head')
      head.insert('b', 'a')
      head.insert('c', 'b')
      head.insert('d', 'c')
      head.insert('e', 'd')
      head.insert('a', 'e') // 形成环

      /**
       * 格式化链表 结果写在页面
       */
      function wirteContainer() {
        let node = head.head.next // 从第一个实际节点开始
        let str = ''

        // 防止无限循环
        let visited = new Set()
        while (node && !visited.has(node)) {
          str += node.ele + ' -> '
          visited.add(node)
          node = node.next
        }
        str += node ? 'cycle detected' : 'null'
        container.innerHTML =
          str + '<br />' + (detectCycle2(head.head) ? '存在环' : '不存在环')
      }

      /**
       * 环形链表判断
       * @param head ListNode类
       * @return bool布尔型
       */
      function detectCycle(head) {
        // 快慢指针初始化指向 head
        let slow = head
        let fast = head

        // 快指针走到末尾时停止
        while (fast && fast.next) {
          // 慢指针走一步，快指针走两步
          slow = slow.next
          fast = fast.next.next

          // 快慢指针相遇，说明含有环
          if (slow == fast) {
            // 任一一节点指向头节点
            fast = head
            // 同步向前进
            while (fast != slow) {
              fast = fast.next
              slow = slow.next
            }
            // 返回入口节点
            console.log(fast)
            return fast
          }
        }
        // 不包含环
        console.log('null')
        return null
      }

      wirteContainer()

      /**
       * 使用哈希表
       */
      function detectCycle2(head) {
        const visited = new Set()
        while (head !== null) {
          if (visited.has(head)) {
            return head
          }
          visited.add(head)
          head = head.next
        }
        return null
      }
    </script>
  </body>
</html>
